package recursivecode.trymodel.rangemodel;

/**
 * 功能描述:获取机器人停车方法编号
 * 2024/07/28
 *
 * @author ZhangYi
 */
public class getRootParkingMethodNumber {
	public static void main(String[] args) {
		// 一共有  多少的 点位
		int M = 7;
		// 当前所在的位置
		int N = 3;
		// 停止的位置
		int P = 2;
		// 剩余可移动的步数
		int K = 3;

		System.out.println(getParkingNumbers(M, P, N, K));
		System.out.println(getParkingNumbersFromCacahe(M, P, N, K));

	}

	/**
	 * 从cacahe获取停车号码
	 *
	 * @param M    m 一共有多少的点位
	 * @param P    p  要停止的位置
	 * @param cur  cur 当前的位置
	 * @param rest rest 剩余的步数
	 * @return int
	 * @author ZhangYi
	 */
	private static int getParkingNumbersFromCacahe(int M, int P, int cur, int rest) {
		if (M < 2 || P > M || cur < 1 || cur > M || rest < 1) {
			return 0;
		}
		int[][] dp = new int[M + 1][rest + 1];
		for (int rowIndex = 0; rowIndex < M + 1; rowIndex++) {
			for (int columnIndex = 0; columnIndex < rest + 1; columnIndex++) {
				dp[rowIndex][columnIndex] = -1;
			}
		}
		return walkCache(M, P, cur, rest, dp);

	}

	/**
	 * 步行移动路径的缓存, 二维数组的缓存
	 *
	 * @param M    m
	 * @param P    p
	 * @param cur  cur
	 * @param rest 休息
	 * @param dp   dp
	 * @return int
	 * @author ZhangYi
	 */
	private static int walkCache(int M, int P, int cur, int rest, int[][] dp) {
		if (dp[cur][rest] != -1) {
			return dp[cur][rest];
		}
		if (rest == 0) {
			dp[cur][rest] = cur == P ? 1 : 0;
			return dp[cur][rest];
		}

		if (cur == 1) {
			dp[cur][rest] = walkCache(M, P, 2, rest - 1, dp);
			return dp[cur][rest];
		}
		if (cur == M) {
			dp[cur][rest] = walkCache(M, P, M - 1, rest - 1, dp);
			return dp[cur][rest];
		}
		dp[cur][rest] = walkCache(M, P, cur - 1, rest - 1, dp) + walkCache(M, P, cur + 1, rest - 1, dp);
		return dp[cur][rest];
	}

	/**
	 * 获取机器人到达指定位置的方法数
	 *
	 * @param M    m
	 * @param P    p
	 * @param cur  cur
	 * @param rest 休息
	 * @return int
	 * @author ZhangYi
	 */
	private static int getParkingNumbers(int M, int P, int cur, int rest) {
		// 如果一共有 1 个点位，则返回0
		if (M < 2) {
			return 0;
		}
		// 如果当前位置小于1，则返回0
		if (cur < 1) {
			return 0;
		}
		// 如果停止的位置小于1，则返回0
		if (P < 1) {
			return 0;
		}
		// 如果停止的位置大于总共的点位数,比如我只有7个位置,停止位置是18;，则返回0
		if (P > M) {
			return 0;
		}
		// 如果剩余的步数小于1，则返回0
		if (rest < 1) {
			return 0;
		}

		return process(M, P, cur, rest);
	}

	/**
	 * 流程
	 *
	 * @param M    m
	 * @param P    p
	 * @param cur  cur
	 * @param rest 剩余的步数
	 * @return int
	 * @author ZhangYi
	 */
	private static int process(int M, int P, int cur, int rest) {
		// 如果剩余的移动步数为0，则判断当前位置是否等于停止的位置, 如果相等则返回1，否则返回0
		if (rest == 0) {
			return cur == P ? 1 : 0;
		}
		// 如果当前位置为1，则只能向右移动
		if (cur == 1) {
			return process(M, P, 2, rest - 1);
		}
		// 如果当前位置为M，则只能向左移动
		if (cur == M) {
			return process(M, P, M - 1, rest - 1);
		}
		// 如果当前位置为在中间,那么她可以继续向左或者向右移动; 统计对应的到达的方法数, 然后相加
		return process(M, P, cur - 1, rest - 1) + process(M, P, cur + 1, rest - 1);
	}


}
